/*
题目: 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。
https://leetcode.cn/problems/maximum-subarray/
 */
public class MaxSubArray {
    public int maxSubArray(int[] nums) {
        return divide(nums, 0, nums.length - 1);
    }

    private int divide(int[] nums, int start, int end) {
        if (start == end) // 如果只有一个元素, 这个元素就是该情况的最大子数组
            return nums[start];

        int mid = start + ((end - start) >> 1);
        int left = divide(nums, start, mid);
        int right = divide(nums, mid + 1, end);

        return Math.max(left, Math.max(right, getMidValue(nums, start, mid, end)));
    }

    private int getMidValue(int[] nums, int start, int mid, int end) {
        int leftSum = Integer.MIN_VALUE;
        for (int i = mid, sum = 0; i >= start; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }

        int rightSum = Integer.MIN_VALUE;
        for (int i = mid + 1, sum = 0; i <= end; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }

        return leftSum + rightSum;
    }
}
